Because the invention seeks to improve the operation of a particular class of string encoder as well as perfect a match to a conditional binary symbol source, prior art bearing on both aspects is believed pertinent. In the following paragraphs reference is made first to LIFO/FIFO arithmetic coding and then to one prior method of source (state) encoder conditioning in order to couple the encoder to a statistical symbol source.
Arithmetic coding was introduced by Rissanen, "Generalized Kraft Inequality and Arithmetic Coding", IMB Journal of Research and Development, Volume 20, Number 3, May 1976, at pages 198-203. In this regard, arithmetic coding is a method applicable to source encoding for purposes of data compression. The source alphabet can be of any size. However, the basic coding operation is add and shift, rather than concatenate and shift. The quantity added to the code strings is called an "augend" and is always a fixed number of bits long. The "shift amount" is a function of the symbol probability. The decoder decodes each symbol by magnitude comparison. Thus, the code string is treated as a magnitude which, for decoder convenience, can be set to lie in the range between zero and one. When the decoder determines the value of the symbol, it subtracts out the augend corresponding to that symbol. The decoder then shifts the result left by the corresponding shift amount.
Langdon, et al, U.S. Pat. No. 4,122,440, "Method and Means for Arithmetic String Coding", issued Oct. 24, 1978, taught that arithmetically encoded strings could be compressed to an efficiency approximating, within a predetermined amount, the entropy. The advance in this case relied on using only a limited amount of information from the last code word generated in order to calculate the new code word. Consequently, a compressor/decompressor became physically realizable because a buffer of only finite length was required. Applications were restricted because of the manner by which the code characters were generated, i.e., shifting to the right. This resulted in LIFO decoding. LIFO decoding means that the least significant bits are generated first, while the most significant bits are generated last. Consequently, decoding cannot occur until the entire code string has been received and/or assembled. In FIFO operations, the most significant bits are generated first and hence, decoding can occur without delay.
One example of FIFO string encoding is to be found in R. C. Pasco, "Source Coding Algorithms for Fast Data Compression", doctoral thesis, Department of Electrical Engineering, Stanford University, May 1976. In this thesis, Pasco disclosed a method of arithmetic coding in which the updating of the encoded string uses the multiplication operation performed upon operands selected according to their relative probabilities of symbol occurrence. Pasco's use of multiplication for updating required that for each m bit operand multiplied by an n bit operand, then m+n bits of precision would have had to be maintained. Although FIFO decoding was possible, it required the processing of the entire string prior to transmission and/or storage. The reason for this was that Pasco did not control his "carry".
The arithmetic encoding process can be viewed as the summation of properly shifted numbers as may be found, for example, in the process of ordinary multiplication, where individual summands are the augends and the displacements in digits between adjacent augends are the shift amounts. In this regard, see the Langdon, et al, patent and Rissanen and Langdon, "Arithmetic Coding", IBM Journal of Research and Development, Volume 23, Number 2, pages 149-162, March 1979.
We formulate an analogy of encoding with ordinary multiplication. In ordinary multiplication, some augends may be zero, as in arithmetic coding, but the shift amount is always one. Also, in ordinary multiplication, as in LIFO-type arithmetic codes, each augend is added to the sum of the previous right-most augend. In ordinary multiplication, this is called a partial product. For arithmetic coding purposes, it is termed a partial sum.
In ordinary multiplication, once bit positions have exited to the right of the arithmetic part of the summation operation, they are never changed. In LIFO arithmetic codes, the summation begins at the least significant augend, whereas for the FIFO codes, the summation begins with the most significant augend. For FIFO codes, the carry-over presents a problem because the partial sums are generated beginning with the most significant augend. This is because bit positions which have already undergone the summation process are still subject to being "one-upped" due to the propagation of a carry.
The "carry-over problem" with respect to FIFO arithmetic codes may be understood by way of an encoder at the working end of a code string outputting a string of consecutive ones, then a "one" added to the lowest order "one" would cause a carry to propagate left until stopped by a zero. Copending U.S. Patent application U.S. Ser. No. 048,318 filed June 14, 1979, "A Method and Means for Carry-over Control in the High Order to Low Order Pairwise Combining of Digits of a Decodable Set of Relatively Shifted Finite Number Strings", Langdon and Rissanen, described FIFO code string generation requiring only the insertion of a control character after the detection of a run of consecutive "ones" in the code string. This control character insertion caused the decoder to be operated in an overflow mode. The key was in the invocation of the decoder to share overflow (carry propagation management) and not place the entire burden upon the encoding cycle.
The success of coding a source alphabet for the purpose of compression depends upon the source statistics, i.e., the individual symbol probabilities of the source. Ideally, a compression code uses shorter code words from the code alphabet for the more probable source symbols and longer code words for the less probable symbols. Ideally, short code words should be assignable to all source symbols. However, in order to decode such an encoded string, a binary code alphabet can only have two code words of length one, i.e., zero or one. Indeed, if zero and one are used as single code words, then there is no room for longer code words and still have the code uniquely decodable. As a result, when the source is binary there have been attempts in the art to encode "events" which represent a group of source symbols at a time. The simplest example of this is alphabet extension, where 0 0, 0 1, 1 0, and 1 1 may be treated as a four-symbol alphabet. Another example of increasing the number of events to be encoded is called run-length coding. The repetition factor of the most probable symbol is encoded.
A source conditioning function maps the past history of the source into a set of conditioning states. Source conditioning is application dependent and is part of the prior art of code design. In a simple example, the "first order" Markov source takes as the current state, the value of the last symbol emitted from the source. In two-dimensional black and white facsimile coding, the state used by Preuss is a previously transmitted neighborhood of the pel to be encoded. Preuss' teaching appeared in the 1975 conference record IEEE on Communications, Volume One, June 16-18, at pages 7/12-7/16, "Comparison of Two Dimensional Facsimile Coding Schemes".
Preuss pointed out that with a four-picture element neighborhood, with each pel being zero (white) or one (black), there are 2.sup.4, or 16 states. Each state n has conditional probabilities p(0/n) and p(1/n) for the encoded pel being respectively white or black. As is well known, integer length code word codes for binary sources assigned code word "0" to symbol zero and "1" to symbol one, resulting in no compression. To avoid this problem, Preuss constructed individual runs (strings of consecutive zeros or consecutive ones) for each state appearance. The appearances themselves were not, in general, consecutive. Consequently, for each such state, the runs were accumulated during a document scan. After scanning, an associated encoder transmitted the run-lengths for the first state, second state, etc. Since the state did not appear in this order, the decoder was required to receive the entire transmission and then reconstruct the documents from the run-length. Again, the method is not instantaneous as the decoder must receive at least most of the encoded document before it can start to decode.